home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 17 / CU Amiga Magazine's Super CD-ROM 17 (1997)(EMAP Images)(GB)[!][issue 1997-12].iso / CUCD / Programming / DiceSource / lib / stdlib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-09-09  |  1.7 KB  |  83 lines
  1.  
  2. /*
  3.  *  QSORT.C
  4.  *
  5.  *    (c)Copyright 1992-1997 Obvious Implementations Corp.  Redistribution and
  6.  *    use is allowed under the terms of the DICE-LICENSE FILE,
  7.  *    DICE-LICENSE.TXT.
  8.  *
  9.  *  Well, I actually implement a merge sort here, because I have no idea
  10.  *  how much stack is available for a quick sort.
  11.  */
  12.  
  13. #include <stdlib.h>
  14. #include <string.h>
  15.  
  16. void
  17. qsort(base, elms, elmSize, cmpfunc)
  18. void *base;
  19. size_t elms;
  20. size_t elmSize;
  21. int (*cmpfunc)(const void *, const void *);
  22. {
  23.     long i, j;
  24.     void *tmp = malloc(elmSize);
  25.  
  26.     if (tmp == NULL)
  27.     return;
  28.  
  29.     for (i = 2; (i >> 1) < elms; i *= 2) {       /*  merge sets of 2,4,8.. */
  30.     for (j = 0; j < elms; j += i) {
  31.         long i1 = i >> 1;
  32.         long i2 = i1;
  33.         char *p1;
  34.         char *p2;
  35.  
  36.         if (elmSize == 4) {
  37.         p1 = (char *)base + j * 4;
  38.         p2 = p1 + i1 * 4;
  39.         } else {
  40.         p1 = (char *)base + j * elmSize;
  41.         p2 = p1 + i1 * elmSize;
  42.         }
  43.  
  44.         if (j + i1 + i2 > elms)
  45.         i2 = elms - i1 - j;
  46.  
  47.         /*
  48.          *    Merge p2/i2 into p1/i1 until p2/i2 is exausted.  Note that
  49.          *    i2 might start out negative (in which case i1 is invalid,
  50.          *    but the segment is already sorted anyway)
  51.          */
  52.  
  53.         while (i2 > 0 && i1 > 0) {
  54.         /*
  55.          *  compare current p1/i1 with next p2/i2.  Skip p1 while
  56.          *  p1 < p2.  Otherwise, merge the p2/i2 element into
  57.          *  p1/i1.
  58.          */
  59.  
  60.         if ((*cmpfunc)(p1, p2) <= 0) {
  61.             --i1;
  62.             p1 += elmSize;
  63.         } else {
  64.             if (elmSize == 4) {
  65.             *(long *)tmp = *(long *)p2;
  66.             movmem(p1, p1 + 4, i1 * 4);
  67.             *(long *)p1 = *(long *)tmp;
  68.             } else {
  69.             movmem(p2, tmp, elmSize);
  70.             movmem(p1, p1 + elmSize, i1 * elmSize);
  71.             movmem(tmp, p1, elmSize);
  72.             }
  73.             --i2;
  74.             p2 += elmSize;
  75.             p1 += elmSize;    /*  shifted p1, i1 stays    */
  76.         }
  77.         }
  78.     }
  79.     }
  80.     free(tmp);
  81. }
  82.  
  83.